package Atop100.listNode;

import java.util.HashMap;

public class LRUreview10_29 {
        class  Node<K,V>{
            K key;
            V value;
            Node  pre;
            Node  next;
            public  Node(){
                this.pre=null;
                this.next=null;
            }
            public Node(K key,V value){
                this.key=key;
                this.value=value;
                this.pre=null;
                this.next=null;
            }
        }

        class DoubleLinkedList<K,V>{
            Node<K,V> head;
            Node<K,V>  tail;

            public DoubleLinkedList(){

                //TODO:2023/10/29 需要定义head 和pre
                 head=new Node<>();
                 tail=new Node<>();
                head.next=tail;
                tail.pre=head;
            }
            public void  addHead(Node node){
                node.pre=head;
                node.next=head.next;
                head.next.pre=node;
                head.next=node;
            }

            public  void  removeNode(Node node){
                node.pre.next=node.next;
                node.next.pre=node.pre;
                node.next=null;
                node.pre=null;
            }

            public Node  getLast(){
                return tail.pre;
            }

        }

        HashMap<Integer,Node<Integer,Integer>> map;
        DoubleLinkedList<Integer,Integer> doubleLinkedList;
        int  capacity;
        public LRUreview10_29 (int capacity) {
            this.map=new HashMap<>();
            this.doubleLinkedList=new DoubleLinkedList<>();
            this.capacity=capacity;
        }
        public int get(int key) {
            if(map.containsKey(key)){
                Node node=  map.get(key);
                doubleLinkedList.removeNode(node);
                doubleLinkedList.addHead(node);
                return (int) node.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            if(map.containsKey(key)){
                Node node=map.get(key);
                node.value=value;
                map.put(key,node);
                doubleLinkedList.removeNode(node);
                doubleLinkedList.addHead(node);
            }else{
                if(map.size()==capacity){
                    Node last= doubleLinkedList.getLast();
                    map.remove(last.key);
                    doubleLinkedList.removeNode(last);
                }
                Node newNode=new Node(key,value);
                map.put(key,newNode);
                doubleLinkedList.addHead(newNode);
            }

        }
    }



